package com.zj.leetcode.easy.greed;

/**
 * @program: algorithm
 * @description: 最大子数组和
 * 53 maximum-subarray
 * @author: Zhang Bo
 * @create: 2022-04-06 11:08:49
 **/
public class MaximumSubarray {

//    nums = [-2,1,-3,4,-1,2,1,-5,4]

    public static void main(String[] args) {
        Solution solution = new MaximumSubarray().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxSubArray(int[] nums) {

            int count = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                int max = 0;
                for (int j = i; j < nums.length; j++) {
                    max += nums[j];
                    count = Math.max(count, max);
                }
            }
            return count;

        }

        public int maxSubArray01(int[] nums) {

            int max = 0;
            int ret = nums[0];
            for (int num : nums) {
                max = Math.max(max + num, num);
                ret = Math.max(ret, max);
            }

            return ret;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
